package code.BinaryTree;

import struct.Tree;
import struct.TreeNode;

//打印二叉树的边界节点
public class PrintEdge {
	public static void main(String[] args) {

		TreeNode tree = Tree.constructTree("[1,2,3,null," +
				"4,5,6,7,8,9,10,null,null,null,null,null,11,12,null,null,null," +
				"13,14,15,16]");

		PrintEdge printEdge = new PrintEdge();

		printEdge.printEdge1(tree);
	}

	public void printEdge1(TreeNode head) {
		if (head == null) {
			return;
		}
		TreeDepth maxDepth = new TreeDepth();
		int h = maxDepth.maxDepth(head);
		TreeNode[][] treeNodes = new TreeNode[h][2];
		System.out.println(treeNodes.length);
		setEdgeNodes(head, treeNodes, 0);
		for (int i = 0; i < treeNodes.length; i++) {
			System.out.print(treeNodes[i][0].val + " ");
		}
		printEdge1Leaf(head, treeNodes, 0);
		for (int i = treeNodes.length - 1; i >= 0; i--) {
			if (treeNodes[i][1].val != treeNodes[i][0].val) {
				System.out.print(treeNodes[i][1].val + " ");
			}
		}
	}

	public void setEdgeNodes(TreeNode head, TreeNode[][] treeNodes, int h) {
		if (head == null) {
			return;
		}
		if (treeNodes[h][0] == null) {
			treeNodes[h][0] = head;
		}
		treeNodes[h][1] = head;
		setEdgeNodes(head.left, treeNodes, h + 1);
		setEdgeNodes(head.right, treeNodes, h + 1);
	}

	public void printEdge1Leaf(TreeNode head, TreeNode[][] treeNodes, int h) {
		if (head == null) {
			return;
		}

		if (head.left == null && head.right == null && head != treeNodes[h][0] && head != treeNodes[h][1]) {
			System.out.print(head.val + " ");
		}
		printEdge1Leaf(head.left, treeNodes, h + 1);
		printEdge1Leaf(head.right, treeNodes, h + 1);
	}
}
